package heap_queue

import (
	"go-guide/utils/intefaces"
)

type MaxHeap struct {
	data       []interface{}
	capacity   int
	size       int
	loadFactor float32
}

func NewMaxHeap(capacity int) *MaxHeap {
	return &MaxHeap{
		data:       make([]interface{}, capacity),
		capacity:   capacity,
		size:       0,
		loadFactor: 0.75,
	}
}

func (m *MaxHeap) Size() int {
	return m.size
}

func (m *MaxHeap) Capacity() int {
	return m.capacity
}

func (m *MaxHeap) Add(e interface{}) {

	curFactor := float32(m.size) / float32(m.capacity)
	if curFactor >= m.loadFactor {
		m.resize()
	}
	m.data[m.size] = e
	m.siftUp(m.size)
	m.size++
}

func (m *MaxHeap) ExtractMax() {
	m.data[0] = m.data[m.size-1]
	m.data[m.size-1] = nil
	m.size--
	m.siftDown(0)
}

// 返回搜索目标值的索引，如果不存在返回索引
// 在实际情况下，这个时间复杂度是O(n)
// 不建议使用堆这种数据结构，堆主要用在移除最大值和最小值
func (m *MaxHeap) getIndex(e interface{}) int {

	for i := 0; i < m.size; i++ {
		if intefaces.Compare(e, m.data[i]) == 0 {
			return i
		}
	}
	return -1
}

func (m *MaxHeap) resize() {
	newData := make([]interface{}, m.capacity<<1)
	for i := 0; i < m.size; i++ {
		newData[i] = m.data[i]
	}
	m.data = nil
	m.data = newData
	m.capacity = m.capacity << 1
}

func (m *MaxHeap) FindMax() interface{} {
	if m.size == 0 {
		panic("can find max when heap is empty")
	}
	return m.data[0]
}

// 上浮
func (m *MaxHeap) siftUp(k int) {
	for k > 0 && intefaces.Compare(m.data[parent(k)], m.data[k]) < 0 {
		swap(m.data, k, parent(k))
		k = parent(k)
	}
}

// 下沉
func (m *MaxHeap) siftDown(k int) {
	if left(k) < m.size || right(k) < m.size && (intefaces.Compare(m.data[left(k)], m.data[k]) > 0 || intefaces.Compare(m.data[right(k)], m.data[k]) > 0) {
		if intefaces.Compare(m.data[left(k)], m.data[right(k)]) > 0 {
			swap(m.data, left(k), k)
			k = left(k)
		} else {
			swap(m.data, right(k), k)
			k = right(k)
		}
		m.siftDown(k)
	}
}

// Replace 取出堆中的最大元素，并且替换成元素e
func (m *MaxHeap) Replace(e interface{}) interface{} {
	ret := m.FindMax()
	m.data[0] = e
	m.siftDown(0)
	return ret
}

// heapify: 将任意数组整理成堆的形状
// 基本思想: 就是从最后一个非叶子节点开始进行下沉操作

func Heapify(arr *[]interface{}) *MaxHeap {
	n := len(*arr)
	from := parent(n)
	maxHeap := &MaxHeap{
		data:       *arr,
		capacity:   n * 2,
		size:       n,
		loadFactor: 0.75,
	}
	for from >= 0 {
		maxHeap.siftDown(from)
		from--
	}
	return maxHeap
}

// data[j] 是 leftChild 和 rightChild 中的最大值
//func (m *MaxHeap) siftDown(k int) {
//	for left(k) < m.size {
//		j := left(k)
//		// j+1是右孩子索引，如果存在右孩子比较后获得左右孩子中较大值的索引
//		if j+1 < m.size && intefaces.Compare(m.data[j+1], m.data[j]) > 0 {
//			j++
//		}
//		// data[j] 是 leftChild 和 rightChild 中的最大值
//		if intefaces.Compare(m.data[k], m.data[j]) > 0 {
//			break
//		}
//
//		swap(m.data, k, j)
//		k = j
//	}
//}

func swap(data []interface{}, i int, j int) {
	tmp := data[i]
	data[i] = data[j]
	data[j] = tmp
}

func left(i int) int {
	return 2*i + 1
}

func right(i int) int {
	return 2*i + 2
}

func parent(i int) int {
	if i == 0 {
		panic("index 0 does not have parent")
	}
	ret := (i - 1) / 2
	return ret
}
